package leetcode_200;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import helpclass.UndirectedGraphNode;

/**
 *@author 周杨
 *CloneGraph_133 复制一个图
 *describe:用深度优先遍历 AC 100%
 *2018年5月30日 上午11:57:50
 */
public class CloneGraph_133 {
	Map<Integer,UndirectedGraphNode> visited=new HashMap<Integer,UndirectedGraphNode>();
	public static void main(String[] args) {
		CloneGraph_133 test=new CloneGraph_133();
		UndirectedGraphNode root1=new UndirectedGraphNode(1);
		UndirectedGraphNode root0=new UndirectedGraphNode(0);
		UndirectedGraphNode root2=new UndirectedGraphNode(2);
		
		
		root1.neighbors=new ArrayList<UndirectedGraphNode>();
		root1.neighbors.add(root0);
		root1.neighbors.add(root2);
		
		root0.neighbors=new ArrayList<UndirectedGraphNode>();
		root0.neighbors.add(root1);
		root0.neighbors.add(root2);
		
		root2.neighbors=new ArrayList<UndirectedGraphNode>();
		root2.neighbors.add(root1);
		root2.neighbors.add(root0);
		root2.neighbors.add(root2);
		
		UndirectedGraphNode res=test.cloneGraph(root1);

	}
	public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
	        if(node==null)
	        	return null;
	        UndirectedGraphNode res=new UndirectedGraphNode(node.label);
	        UndirectedGraphNode run=res;
	        help(run,node);
	        return res;
	}
	
	public void help(UndirectedGraphNode run,UndirectedGraphNode node) {
			run.neighbors=new ArrayList<UndirectedGraphNode>();
			visited.put(node.label,run);
			for(UndirectedGraphNode next:node.neighbors) {
				if(next.label==node.label) {//成环
					run.neighbors.add(run);
				}
				else {
					UndirectedGraphNode now=visited.get(next.label);
					if(now==null) {//没有遍历过
						UndirectedGraphNode newNode =new UndirectedGraphNode(next.label);
						run.neighbors.add(newNode); 
						help(newNode,next);
					}
					else {
						run.neighbors.add(now);
					}
						
				}
			}
	}
}
